package LeetCode.BitCompute;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * 260. 只出现一次的数字 III
 * https://leetcode-cn.com/problems/single-number-iii/description/
 * <p>
 * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。
 * 找出只出现一次的那两个元素。
 * <p>
 * 示例 :
 * 输入: [1,2,1,3,2,5]
 * 输出: [3,5]
 * <p>
 * 注意：
 * 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
 * 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
 */
public class Test4 {

    public static int[] singleNumber(int[] nums) {
        //线性时间复杂度思路：遍历数组，使用HashSet保存结果，
        // 如果原来集合HashSet里没有则添加，如果HashSet里有则删除，最后只留下出现一次的数据。
        HashSet set = new HashSet();
        for (int i : nums) {
            if (set.contains(i)) {
                set.remove(i);
            } else {
                set.add(i);
            }
        }
//        System.out.println("集合大小"+set.size());
        int[] result = new int[set.size()];
        Iterator<Integer> iterator = set.iterator();
        int i = 0;
        while (iterator.hasNext()) {
            result[i++] = iterator.next();
        }
        return result;
    }


    //位运算:常熟时间复杂度
//    public static int[] singleNumber2(int[] nums) {
//    }

    public static void main(String[] args) {
        System.out.println("位运算：只出现一次的数字 III");
        int[] nums = {1,2,1,3,2,5};

        int[] nums2 = singleNumber(nums);
        for (int i : nums2) {
            System.out.println(i);
        }
    }
}
